package com.origin.niuke.tree;

import general_class.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/6/8 21:45
 * 对称的二叉树
 * 算法：递归、迭代
 */
public class NC16 {

    boolean isSymmetrical(TreeNode pRoot) {
        return recursion(pRoot, pRoot);
    }
    boolean recursion(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) return true;
        if (root1 == null || root2 == null || root1.val != root2.val) return false;
        return recursion(root1.left, root2.right) && recursion(root1.right, root2.left);
    }

    boolean isSymmetrical2(TreeNode pRoot) {
        if (pRoot == null) return true;
        Deque<TreeNode> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>();
        d1.addLast(pRoot);
        d2.addLast(pRoot);
        while (!d1.isEmpty()) {
            if (d2.isEmpty()) return false;
            TreeNode t1 = d1.pollFirst(), t2 = d2.pollFirst();
            if (t1.left != null && t2.right == null) return false;
            if (t1.left == null && t2.right != null) return false;
            if (t1.left != null && t2.right != null) {
                if (t1.left.val != t2.right.val) return false;
                d1.addLast(t1.left); d2.addLast(t2.right);
            }
            if (t1.right != null && t2.left == null) return false;
            if (t1.right == null && t2.left != null) return false;
            if (t1.right != null && t2.left != null) {
                if (t1.right.val != t2.left.val) return false;
                d1.addLast(t1.right); d2.addLast(t2.left);
            }
        }
        return d2.isEmpty();
    }

}
